package com.wj.algorithm.lintcode.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class P171 {
    public int charToInt(char ch) {
        return ch - 'a';
    }

    public String createKey(String s) {
        int[] arr = new int[s.length()];
        for(int i = 0, len = s.length(); i < len; i ++) {
            arr[i] = charToInt(s.charAt(i));
        }
        
        Arrays.sort(arr);
        StringBuilder b = new StringBuilder();
        for(int i : arr) {
            b.append(i).append("_");
        }
        
        return b.toString();
    }
    
    public List<String> anagrams(String[] strs) {
        List<String> list = new ArrayList<String>();

        Map<String, String> temp = new HashMap<String, String>();
        for(String s : strs) {
            String key = createKey(s);
            
            if(temp.containsKey(key)) {
                list.add(s);
                String t = temp.get(key);
                if(t != null) {
                    list.add(t);
                    temp.put(key, null);
                }
            } else {
                temp.put(key, s);
            }
        }
        return list;
    }
    
    public static void main(String[] args) {
        System.out.println(new P171().anagrams(new String[]{"lint","intl","inlt","code"}));
    }
}
